package binarytree;

import java.util.*;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 实现二叉树的基本操作
 */
@SuppressWarnings({"all"})
public class BinaryTree {

    static class TreeNode {

        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    /**
     * 创建一棵二叉树 返回这棵树的根节点
     * @return
     */
    public TreeNode createTree() {
        // 先使用朴素穷举的方式构建一个二叉树 方便测试
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        e.right = h;
        c.left = f;
        c.right = g;
        return a;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 前序遍历非递归
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                res.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return res;
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 中序遍历非递归
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            res.add(top.val);
            cur = top.right;
        }
        return res;
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 后序遍历非递归
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode pre = null; // 标记是否遍历过
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || pre == top.right){
                res.add(top.val);
                pre = top;
                stack.pop();
            }else{
                cur = top.right;
            }
        }
        return res;
    }

    /**
     * 获取树中节点的个数：遍历思路
     */
    public static int nodeSize; // 表示树的节点个数 但是成员方式仅第一次调用不会出错
    void size(TreeNode root) {
        // 如果树为空
        if (root == null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数：子问题的思路
     * @param root
     * @return 返回节点数量
     */
    int size2(TreeNode root) {
        // 如果树为空
        if (root == null){
            return 0;
        }
        // 分解为子问题：树的节点个数 = 左子树的节点个数 + 右子树的节点个数 + 1
        int leftCount = size2(root.left);
        int rightCount = size2(root.right);
        return leftCount + rightCount + 1;
    }

    /**
     * 获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0; // 表示叶子节点数量
    void getLeafNodeCount1(TreeNode root) {
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /**
     * 获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        int leftLeaf = getLeafNodeCount2(root.left);
        int rightLeaf = getLeafNodeCount2(root.right);
        return leftLeaf + rightLeaf;
    }

    /**
     * 获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        // 如果树为空
        if (root == null){
            return 0;
        }
        // 对于每个以root为节点的子树而言，k=1时，节点数为1
        if (k == 1){
            return 1;
        }
        // 对于root而言，其k层的节点个数为其左子树第k-1层的节点数与右子树第k-1层的节点数之和
        // 对于每一个子树而言，其k层的节点个数依然为其左右子树k-1层的节点数之和
        int leftCount = getKLevelNodeCount(root.left, k-1);
        int rightCount = getKLevelNodeCount(root.right, k-1);
        return leftCount + rightCount;
    }

    /**
     * 获取二叉树的高度
     * 时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if (root == null){
            return 0;
        }
        // 树的高度为其左子树和右子树高度的较大值＋1
        int leftHeigh = getHeight(root.left);
        int rightHeigh = getHeight(root.right);
        return leftHeigh > rightHeigh ? leftHeigh + 1 : rightHeigh + 1;
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        TreeNode leftTree = find(root.left, val);
        if (leftTree != null){
            return leftTree;
        }
        TreeNode rightTree = find(root.right, val);
        if (rightTree != null){
            return rightTree;
        }
        return null;
    }
//
    // 层次遍历
    void levelOrder(TreeNode root) {
        // 使用队列来解决
        if (root == null){
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
//
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        // 使用队列
        if(root == null){
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll != null){
                queue.offer(poll.left);
                queue.offer(poll.right);
            }else {
                break;
            }
        }
        // 判断剩余元素是否存在非空
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll != null){
                return false;
            }
        }
        return true;
    }

    // 层序遍历 并存储为list
    public List<List<Character>> levelOrderToList(TreeNode root) {
        List<List<Character>> res = new LinkedList<>();
        if(root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Character> list = new LinkedList<>();
            int size = queue.size();
            while (size-- != 0){
                TreeNode cur = queue.poll();
//                System.out.print(cur.val+" ");
                list.add(cur.val);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(list);
        }
        return res;
    }

    /**
     * 获取从根root到指定节点node的路径 并用stack存储
     * @param root
     * @param node
     * @param stack
     * @return
     */
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if(root == null || node == null)return false;
        stack.push(root);
        //放完之后 要检查
        if(root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1) return true;
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) return true;
        stack.pop();
        return false;
    }

    /**
     * 寻找p q节点的最近公共祖先
     * @param root 根节点
     * @param p
     * @param q
     * @return 返回公共祖先
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        //1、两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2、判断栈的大小
        if(stack1.size() < stack2.size()){
            Deque<TreeNode> temp = stack1;
            stack1 = stack2;
            stack2 = temp;
        }
        //3、出栈对齐
        while(stack1.size() != stack2.size()){
            stack1.pop();
        }
        //4、依次出栈比较
        while (stack1.size() != 0 && stack2.size() != 0){
            TreeNode ret = stack1.pop();
            if (ret == stack2.pop()){
                return ret;
            }
        }
        return null;
    }

    // 公共祖先的递归实现
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        // 寻找到 p 或 q 则说明当前节点就是公共节点
        if(root == p || root == q){
            return root;
        }
        // 先向左 后向右子树寻找
        TreeNode leftRet = lowestCommonAncestor(root.left, p, q);
        TreeNode rightRet = lowestCommonAncestor(root.right, p, q);
        // 左右子树都能找到 说明当前节点就是公共祖先
        if(leftRet != null && rightRet != null){
            return root;
        }else if(leftRet != null){
            // 左子树的返回节点是公共祖先
            return leftRet;
        }else if(rightRet != null){
            // 右子树的返回节点是公共祖先
            return rightRet;
        }
        return null;
    }

    // 二叉树的层次遍历 自底向上 即正常的层次遍历结果的逆序
    // 头插法 + 队列实现
    public List<List<Character>> levelOrderBottom(TreeNode root) {
        // 自底向上层序遍历 考虑按照层序遍历的方式 将每一层头插到结果的头部
        List<List<Character>> levelOrder = new LinkedList<>();
        if(root == null){
            return levelOrder; //[]输入返回[]
        }
        // 使用队列进行层序遍历
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 先入根节点
        while(!queue.isEmpty()){
            List<Character> level = new LinkedList<>(); // 存储每一层的序列
            int curSize = queue.size(); // 获取当前队列的节点数量 表示当前层有多少个元素
            while(curSize-- != 0){
                TreeNode curNode = queue.poll();
                if(curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
                level.add(curNode.val); // 加入当前节点的值
            }
            // 将每一层头插到结果的头部
            levelOrder.add(0, level);
        }
        return levelOrder;
    }

    static int  i = 0; // 用于遍历字符串
    // 根据先序遍历序列构建二叉树 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
    public static TreeNode createTree2(String str){
        // 如果遇到“#”则为空
        if(str.charAt(i) == '#'){
            i++;
            return null;
        }
        // 否则按照val构造树节点
        TreeNode root = new TreeNode(str.charAt(i));
        i++;
        // 获取左子树和右子树的根节点 构造出二叉树
        root.left = createTree2(str);
        root.right = createTree2(str);
        // 最后将根节点返回
        return root;
    }

    // 根据二叉树生成字符串
    public String tree2str(TreeNode root) {
        StringBuilder res = new StringBuilder();
        // 如果根节点为空
        if(root == null){
            return "";
        }
        res.append(root.val);
        // 分别遍历左子树和右子树
        if(root.left != null){
            // 左子树不为空
            res.append("(");
            res.append(tree2str(root.left));
            res.append(")");
        }else{
            // 左子树为空 右子树不为空
            if(root.right != null){
                res.append("()");
            }else{
                return res.toString();
            }
        }

        if(root.right != null){
            res.append("(");
            res.append(tree2str(root.right));
            res.append(")");
        }else{
            return res.toString();
        }
        return res.toString();
    }
}
